/*
 * @lc app=leetcode.cn id=786 lang=java
 *
 * [786] 第 K 个最小的质数分数
 */

// @lc code=start

import java.util.PriorityQueue;


class Solution {

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        // 使用大根堆
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>(
            (a, b) -> Double.compare(b[0]*1.0 / b[1], a[0]*1.0 / a[1])
        );

        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                double t = arr[i]*1.0 / arr[j];

                if(q.size() < k || t < q.peek()[0]*1.0 / q.peek()[1]) {
                    if(q.size() == k) q.poll();
                    q.offer(new int[]{arr[i], arr[j]});
                }
            }
        }
        return q.poll();
    }

    
}
// @lc code=end

